home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_10_08 / 1008060a < prev    next >
Encoding:
Text File  |  1992-05-27  |  14.1 KB  |  523 lines
  1. /*
  2. Postman's Sort (R) Version 1.0
  3. Copyright (c) Robert Ramey 1991. All Rights Reserved
  4. */
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <time.h>
  9. #include <assert.h>
  10. #include <links.h>
  11. #include "psort.h"
  12. #include "sublist.h"
  13. #include "key.h"
  14. #include "io.h"
  15. #include "os.h"
  16.  
  17. #define FILE_GUESS 50000
  18. #define RECORD_SIZE_GUESS 80
  19. #define NSIZE 31
  20.     /* default maximum number of digits left of radix point */
  21.     /* don't increase this beyond 127 */
  22. #define MAX_BYTES_PER_PASS 8
  23.  
  24. /*********************************************************************
  25. The following structure contains one member for each byte on which a
  26. record may be distributed.  That is, if a sublist is to be distribiuted
  27. on the first two letters of an alphabetic key, the first tow members of
  28. the table will be used.  In this example byte_count will equal 2.
  29. **********************************************************************/
  30. typedef struct {
  31.     unsigned int *value;    /* points to sequence value array */
  32.     unsigned int order;    /* number of possible sequence values for this byte */
  33.     unsigned int count;    /* number of sublists to skip to get to next one */
  34.     unsigned int key_index;    /* index of key where this byte is found */
  35.     unsigned int field_index; /* key_index + 1 */
  36.     unsigned int depth;        /* displacement within key where byte is found */
  37. } BYTE_TABLE;
  38.  
  39. /*********************************************************************
  40. The following data stores the state of sublist arrays and sort keys
  41. **********************************************************************/
  42. typedef struct {
  43.     SUBLIST *sublist;
  44.     unsigned int
  45.         sublist_count,    /* number of sublists at this level */
  46.         byte_count;        /* number of bytes to test on current pass */
  47.     struct {
  48.         unsigned int
  49.             icount, /* number of frames in environment */
  50.             count;    /* number of data frames so far in memory */
  51.         FILE_SIZE
  52.             limit,    /* amount of memory to be cleared to disk at */
  53.                         /* at a time */
  54.             size;    /* amount filled in current frame */
  55.     } frame;
  56.     BYTE_TABLE byte_table[MAX_BYTES_PER_PASS];
  57.                         /* see above for explanation of BYTE TABLE */
  58. } ENVIRONMENT;
  59.  
  60. /*********************************************************************
  61. global data
  62. **********************************************************************/
  63. BOOLEAN uflag = FALSE;        /* unique flag value */
  64. RECORD *(*infunc)();    /* pointer to function which gets next record */
  65. MEM_SIZE seg_length = 16;    /* default size of stack segment */
  66. unsigned int max_sublists = 0;
  67.                         /* maximum number of sublists / segment */
  68. ENVIRONMENT *env_ptr = (ENVIRONMENT *)NULL;
  69.                         /* pointer to current environment */
  70. void
  71. sort();
  72. private void
  73. psort(unsigned int, unsigned int, SUBLIST *);
  74. private unsigned int
  75. plan(ENVIRONMENT *, unsigned int, unsigned int, unsigned long, FILE_SIZE);
  76. private int
  77. dist(SUBLIST *, SUBLIST*);
  78. private void
  79. dsort(SUBLIST *, unsigned int);
  80. private void
  81. nsort(SUBLIST *, unsigned int);
  82. private RECORD *
  83. list_input(SUBLIST *);
  84. private void
  85. fill_fields(RECORD *);
  86. private BOOLEAN
  87. fits(FILE_SIZE, unsigned int);
  88. void *
  89. need(STACK *, size_t);
  90. void *
  91. get_space(STACK *, size_t);
  92. private void
  93. display_out(clock_t);
  94. private clock_t
  95. display_in(unsigned int, unsigned int, long, ENVIRONMENT *);
  96. private void
  97. free_memory(FILE_SIZE);
  98. private void
  99. free_frames(unsigned int);
  100. /*********************************************************************
  101. sort - top level driver for sort engine
  102. **********************************************************************/
  103. void
  104. sort(){
  105.     ENVIRONMENT env;    /* dummy initial environment */
  106.     unsigned int n;
  107.     unsigned long rc;
  108.     FILE_SIZE fsize;
  109.     clock_t time;
  110.  
  111.     /* miniature version of sort */
  112.     /* for a full explanation see below */
  113.  
  114.     /* try to guess file size */
  115.     fsize = os_flength(stdin);
  116.     if(fsize <= 0L)
  117.         fsize = FILE_GUESS;
  118.  
  119.     rc = fsize / (record_size ? record_size : RECORD_SIZE_GUESS);
  120.     n = plan(&env, 0, 0, rc, fsize);
  121.     env.sublist = sublist_allocate(n);
  122.     env.sublist_count = n;
  123.  
  124.     /* initialize stacks */
  125.     assert(stk_push(d_stack));
  126.  
  127.     env.frame.limit = (FILE_SIZE) rb_size * n * K;
  128.     env.frame.size = 0;
  129.     env.frame.icount =
  130.     env.frame.count = 1;
  131.     env_ptr = &env;
  132.  
  133.     sublist_fclose();
  134.  
  135.     time = display_in(0, 0, 0L, &env);
  136.  
  137.     dist((SUBLIST *)NULL, env.sublist);
  138.  
  139.     display_out(time);
  140.  
  141.     infunc = sublist_input;
  142.  
  143.     dsort(env.sublist, 0);
  144.  
  145.     stk_pop(d_stack);
  146.     stk_free(d_stack);
  147.  
  148.     return;
  149. }
  150. /*************************************************************
  151. psort - distribution sort
  152. **************************************************************/
  153. private
  154. void
  155. psort(key_index, depth, sublist)
  156. unsigned int
  157.     key_index,
  158.     depth;
  159. SUBLIST *sublist;
  160. {
  161.     ENVIRONMENT
  162.         *prev_env,    /* pointer to previous environment */
  163.         env;        /* current set fo environment variables */
  164.     clock_t time;    /* used to record time function started */
  165.  
  166.     /* use statics to save stack space for 2nd order recurrsive function */
  167.     static unsigned int n;
  168.                     /* number of sublists needed by on this pass */
  169.     static long record_count;
  170.                     /* number of records in the input sublist */
  171.  
  172.     record_count  = sublist->pcount + sublist->count;
  173.  
  174.     /* take care of end points */
  175.     if(record_count == 0)
  176.         return;
  177.     if(record_count == 1){
  178.         sublist_output(sublist, uflag);
  179.         return;
  180.     }
  181.  
  182.     /* there are no more keys we're done */
  183.     if(key_index >= key_count){
  184.         sublist_output(sublist, uflag);
  185.         return;
  186.     }
  187.  
  188.     /* if current key is exhausted */
  189.     if(depth >= key[key_index].size){
  190.         /* move on to the next one */
  191.         depth = 0;
  192.         /* if that was the last key we're done */
  193.         if(++key_index >= key_count){
  194.             sublist_output(sublist, uflag);
  195.             return;
  196.         }
  197.     }
  198.  
  199.     /* figure out how many key bytes to use in distribution */
  200.     /* and fill them into byte table of new environment */
  201.     n = plan(&env, key_index, depth, record_count, sublist->size);
  202.  
  203.     /* allocate the calculated number of sublists, creating a new */
  204.     /* memory area if necessary */
  205.     env.sublist = sublist_allocate(n);
  206.     env.sublist_count = n;
  207.  
  208.     /* save state of storage */
  209.     /* try to be sure that memory exists for next pass */
  210.     free_memory(sublist->size);
  211.  
  212.     assert(stk_push(d_stack));
  213.     env.frame.limit = (FILE_SIZE) rb_size * n * K;
  214.     env.frame.size = 0;
  215.     env.frame.icount =
  216.     env.frame.count = env_ptr->frame.count+1;
  217.  
  218.     /* close switch to other swap file */
  219.     sublist_fclose();
  220.  
  221.     /* save pointer to previous environment for end of function */
  222.     prev_env = env_ptr;
  223.     env_ptr = &env;
  224.  
  225.     time = display_in(key_index, depth, record_count, &env);
  226.  
  227.     /* distribute the input sublist among the new sublists */
  228.     /* according to the key bytes specified in the byte table*/
  229.     n = dist(sublist, env.sublist);
  230.  
  231.     if(n = 0){
  232.         /* reuse space used by sublist array */
  233.         *sublist = (env.sublist)[n];
  234.         env.sublist = sublist;
  235.         env.sublist_count = 1;
  236.         sublist_shrink();
  237.         dsort(env.sublist, env.byte_count);
  238.     }
  239.     else{
  240.         /* sort sublists in the proper sequence */
  241.         dsort(env.sublist, 0);
  242.     }
  243.  
  244.     /* and recover environment of caller */
  245.     sublist_free();
  246.     do{
  247.         assert(stk_pop(d_stack));
  248.     }while(env.frame.count-- > env.frame.icount);
  249.     env_ptr = prev_env;
  250.     display_out(time);
  251.     return;
  252. }
  253. /*********************************************************************
  254. plan - Figure how many sublists should be created for distributing the
  255. current sublist.  Figure how many bytes should be used to determine
  256. where a record will be distributed.
  257. **********************************************************************/
  258. private
  259. unsigned int
  260. plan(env_ptr, key_index, depth, record_count, fsize)
  261. ENVIRONMENT *env_ptr;/* address of environment where new byte table is*/
  262.                     /* to be loaded */
  263. unsigned int
  264.     key_index,        /* where the next key starts */
  265.     depth;
  266. unsigned long record_count;
  267.                     /* number of records in sublists to be distributed */
  268. FILE_SIZE fsize;    /* total size of sublist records in bytes */
  269. {
  270.     unsigned int i, j, sublist_count;
  271.     BYTE_TABLE *bptr;
  272.  
  273.     /* initialize accumulators */
  274.     env_ptr->byte_count = 0;
  275.     bptr = env_ptr->byte_table;
  276.     sublist_count = 1;
  277.  
  278.     /* figure how many bytes we can handle at a time */
  279.     for(;;){
  280.  
  281.         /* fill byte table entry */
  282.         bptr->value = key[key_index].seq->value;
  283.         bptr->order = key[key_index].seq->order;
  284.         bptr->key_index = key_index;
  285.         bptr->field_index = key_index + 1;
  286.         bptr->depth = depth;
  287.  
  288.         /* figure how many sublists will be created by */
  289.         /* continuing one more level deep */
  290.         i = sublist_count * bptr->order + 1;
  291.  
  292.         if(sublist_count > 1){
  293.  
  294.             /* There is no point in spreading records among too many */
  295.             /* sublists most of which will be empty */
  296.             if(sublist_count > record_count)
  297.                 break;
  298.  
  299.             /* if sublist won't fit into a segment */
  300.             if(i > max_sublists)
  301.                 break;
  302.  
  303.             /* if more sublists won't fit in memory with data */
  304.             if( !fits(fsize, i)){
  305.  
  306.                 /* if blocks written to disk are going to be too small */
  307.                 /* we can quit */
  308.                 if( !fits((FILE_SIZE)i * rb_size * K, i))
  309.                     break;
  310.             }
  311.         }
  312.         sublist_count = i;
  313.  
  314.         /* increment pointer and counter */
  315.         ++bptr;
  316.         ++(env_ptr->byte_count);
  317.  
  318.         /* if this key has been totally checked */
  319.         if(++depth >= key[key_index].size){
  320.             /* if this is the last key */
  321.             if(++key_index == key_count)
  322.                 /* we're done */
  323.                 break;
  324.             /* there are more keys, go on to the next one */
  325.             depth = 0;
  326.         }
  327.     }
  328.  
  329.     /* figure increments at each level of distribution */
  330.     i = 1;
  331.     for(j = env_ptr->byte_count; j-- > 0 ;){
  332.         env_ptr->byte_table[j].count = i;
  333.         i = 1 + i * env_ptr->byte_table[j].order;
  334.     }
  335.     return sublist_count;
  336. }
  337. /*********************************************************************
  338. fits - determine whether or not memory exists for the specified areas
  339. **********************************************************************/
  340. private
  341. BOOLEAN
  342. fits(fsize, scount)
  343. FILE_SIZE fsize;
  344. unsigned int scount;
  345. {
  346.     unsigned int blk_count;
  347.  
  348.     blk_count = stk_unused() + stk_blks(d_stack);
  349.  
  350.     if(scount * sizeof(SUBLIST) > stk_avl(s_stack))
  351.         if(blk_count < 2)
  352.             return FALSE;
  353.         else
  354.             --blk_count;
  355.  
  356.     if((FILE_SIZE)blk_count * seg_length * K + stk_avl(d_stack) > fsize)
  357.         return TRUE;
  358.     else
  359.         return FALSE;
  360. }
  361. /*********************************************************************
  362. dist - Distribute input list among sublists created for this level
  363. of key.  This is the heart of the sort.
  364. **********************************************************************/
  365. private
  366. int
  367. dist(input_sublist, sublist)
  368. SUBLIST *input_sublist, *sublist;
  369. {
  370.     register BYTE_TABLE *bptr;
  371.     RECORD *record_address;
  372.     unsigned int i, j, disp, dcount;
  373.     BOOLEAN hflag;    /* flag to hold output for unique output record */
  374.     BOOLEAN oflag;    /* flag to output directly since no more keys */
  375.     int pdisp;
  376.  
  377.     oflag =
  378.         env_ptr->byte_table[0].key_index == key_count - 1
  379.         ?  TRUE : FALSE;
  380.  
  381.     hflag = FALSE;
  382.  
  383.     dcount =
  384.     disp = 0;
  385.     pdisp = -1;
  386.  
  387.     /* for each record in input list */
  388.     while(record_address = (*infunc)(input_sublist)){
  389.  
  390.         disp = 0;
  391.         bptr = env_ptr->byte_table;
  392.  
  393.         /* check each byte in key */
  394.         i = env_ptr->byte_count;
  395.         do{
  396.             j =bptr->value[/* key table */
  397.                     (record_address->data)[/* record address */
  398.                         record_address->field[/* field pointers */
  399.                             bptr->field_index/* key field index */
  400.                         ] + bptr->depth/* displacement in field */
  401.                     ]
  402.                 ];
  403.             /* if key is terminated prematurly */
  404.             if(j == 0)
  405.                 /* add to sublist in appropriate array */
  406.                 break;
  407.  
  408.             /* accumulate displacement within array of sublists */
  409.             disp += 1 + (j - 1) * (bptr++)->count;
  410.             /* and go on to next byte in key */
  411.  
  412.         /* continue as long as we can check more of the key */
  413.         }while(--i);
  414.  
  415.         /* if last key and key value is the minimum possible */
  416.         if(disp == 0 && oflag){
  417.             /* write record out immediatly */
  418.             if(!hflag)
  419.                 rec_output(record_address);
  420.             /* if unique flag is set, make sure that was the */
  421.             /* record out */
  422.             hflag = uflag;
  423.             /* free up space used by record */
  424.             if(!rec_memflag(record_address))
  425.                 stk_drop(d_stack);
  426.         }
  427.         else{
  428.             if(!rec_memflag(record_address))
  429.                 rec_frame(record_address) = env_ptr->frame.count;
  430.             /* link record into appropriate sublist */
  431.             assert(record_address);
  432.             link(record_address, sublist[disp].memory, 0);
  433.             assert(sublist);
  434.             sublist[disp].memory = record_address;
  435.             ++(sublist[disp].count);
  436.         }
  437.  
  438.         if(disp != pdisp){
  439.             ++dcount;
  440.             pdisp = disp;
  441.         }
  442.     }
  443.     if(dcount > 1)
  444.         return 0;
  445.     else
  446.         return disp;
  447. }
  448. /**********************************************************
  449. dsort - small function to sort sublists in proper sequence.
  450. ***********************************************************/
  451. private
  452. void
  453. dsort(sublist, level)
  454. SUBLIST *sublist;
  455. unsigned level;
  456. {
  457.     unsigned int j;
  458.     BYTE_TABLE *bptr;
  459.  
  460.     if(level == env_ptr->byte_count){
  461.         bptr = &env_ptr->byte_table[level-1];
  462.         psort(bptr->key_index, bptr->depth+1, sublist);
  463.         return;
  464.     }
  465.     bptr = &env_ptr->byte_table[level];
  466.     if(key[bptr->key_index].key_type == SIGN){
  467.         nsort(sublist, level);
  468.         return;
  469.     }
  470.     if(!key[bptr->key_index].inverted){
  471.         psort(bptr->key_index+1, 0, sublist++);
  472.         for(j = 0; j < bptr->order ; ++j){
  473.             dsort(sublist, level+1);
  474.             sublist += bptr->count;
  475.         }
  476.     }
  477.     else{
  478.         sublist += bptr->count * bptr->order + 1;
  479.         for(j = bptr->order; j > 0; --j){
  480.             sublist -= bptr->count;
  481.             dsort(sublist, level+1);
  482.         }
  483.         psort(bptr->key_index+1, 0, --sublist);
  484.     }
  485. }
  486. /**********************************************************
  487. nsort - small function to sort sublists in proper sequence.
  488. special version of dsort for numeric fields.
  489. ***********************************************************/
  490. private
  491. void
  492. nsort(sublist, level)
  493. SUBLIST *sublist;
  494. unsigned int level;
  495. {
  496.     unsigned int key_index;
  497.     int k, j;
  498.     BYTE_TABLE *bptr;
  499.  
  500.     bptr = &env_ptr->byte_table[level];
  501.     key_index = bptr->key_index;
  502.  
  503.     k = bptr->count;
  504.     ++sublist;
  505.     if(key[key_index].inverted){
  506.         sublist += k * bptr->order;
  507.         k *= -1;
  508.     }
  509.     key[key_index+1].inverted = TRUE;
  510.     key[key_index+2].inverted = TRUE;
  511.     for(j = NSIZE; j > 0; --j){
  512.         dsort(sublist, level + 1);
  513.         sublist += k;
  514.     }
  515.     key[key_index+1].inverted = FALSE;
  516.     key[key_index+2].inverted = FALSE;
  517.     for(; j < NSIZE; ++j){
  518.         dsort(sublist, level + 1);
  519.         sublist += k;
  520.     }
  521.     return;
  522. }
  523.